package com.leetcode.partition2;

/**
 * @author `RKC`
 * @date 2021/11/7 9:58
 */
public class LC149直线上最多的点数 {

    public static int maxPoints(int[][] points) {
        if (points.length <= 2) return points.length;
        int ans = 0;
        for (int i = 0; i < points.length; i++) {
            for (int j = i + 1; j < points.length; j++) {
                int x1 = points[i][0], y1 = points[i][1], x2 = points[j][0], y2 = points[j][1];
                //找第三个能和前面两个点斜率相同的点
                int count = 2;
                for (int k = j + 1; k < points.length; k++) {
                    int x3 = points[k][0], y3 = points[k][1];
                    //如果斜率相同，则自加
                    if ((y3 - y2) * (x2 - x1) == (y2 - y1) * (x3 - x2)) {
                        count++;
                    }
                }
                ans = Math.max(ans, count);
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        int[][] points = {{1, 1}, {3, 2}, {5, 3}, {4, 1}, {2, 3}, {1, 4}};
        System.out.println(maxPoints(points));
    }
}
